package com.cango.student.algorithm.leetcode;

import java.util.Arrays;

/**
 * 数组右移K次, 原数组<code> [1, 2, 3, 4, 5, 6, 7]</code> 右移3次后结果为 <code>[5,6,7,1,2,3,4]</code>
 * <p>
 * 基本思路：不开辟新的数组空间的情况下考虑在原属组上进行操作
 * 1 将数组倒置，这样后k个元素就跑到了数组的前面，然后反转一下即可
 * 2 同理后 len-k个元素只需要翻转就完成数组的k次移动
 */
public class ArrayKShift {

    /**
     * 向右移动
     *
     * @param array
     * @param k
     */
    public void arrayKShift(int[] array, int k) {

        /**
         * constrictions
         */

        if (array == null || 0 == array.length) {
            return;
        }

        // 取模
        k = k % array.length;

        if (0 > k) {
            return;
        }

        /**
         * 将数组倒置, e.g: [1, 2, 3 ,4] to [4,3,2,1]
         */
        for (int i = 0; i < array.length / 2; i++) {
            int tmp = array[i];
            array[i] = array[array.length - 1 - i];
            array[array.length - 1 - i] = tmp;
        }

        /**
         * first k element 反转
         */
        for (int i = 0; i < k / 2; i++) {
            int tmp = array[i];
            array[i] = array[k - 1 - i];
            array[k - 1 - i] = tmp;
        }

        /**
         * last length - k element 反转
         */

        for (int i = k; i < k + (array.length - k) / 2; i++) {
            int tmp = array[i];
            array[i] = array[array.length - 1 - i + k];
            array[array.length - 1 - i + k] = tmp;
        }
    }

    public void rotate(int[] nums, int k) {
        // 硬解 空间复杂度O(n^2)
        for (int i = 0; i < k; i++) {
            int tmp = nums[0];
            for (int j = 1; j < nums.length; j++) {

                int t = nums[j];
                nums[j] = tmp;
                tmp = t;
                if (j == nums.length - 1) {
                    nums[0] = tmp;
                }
            }
        }

    }

    /**
     * 向右移动
     *
     * @param array
     * @param k
     */
    public int[] arrayKShift2(int[] array, int k) {
        /**
         * constrictions
         */
        if (array == null || 0 == array.length) {
            return array;
        }

        // 取模
        k = k % array.length;

        if (0 > k) {
            return array;
        }

        int[] temp = new int[array.length];

        for (int i = 0; i < array.length; i++) {
            if (i < array.length - k) {
                temp[k + i] = array[i];
            } else {
                temp[i - (array.length - k)] = array[i];
            }
        }

        return temp;

    }


    /**
     * 向左移动
     *
     * @param array
     * @param k
     */
    public int[] arrayKleft(int[] array, int k) {

        /**
         * constrictions
         */
        if (array == null || 0 == array.length) {
            return array;
        }

        // 取模
        k = k % array.length;



        return arrayKShift2(array, array.length - k);

    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        ArrayKShift shift = new ArrayKShift();

        shift.arrayKShift(array, 15);
        Arrays.stream(array).forEach(o -> {
            System.out.print(o);
            System.out.print(" ");
        });
        System.out.println();
        int[] array2 = {1, 2, 3, 4, 5, 6, 7};
        array2 = shift.arrayKShift2(array2, 5);
        Arrays.stream(array2).forEach(o -> {
            System.out.print(o);
            System.out.print(" ");
        });

        System.out.println();
        int[] array3 = {1, 2, 3, 4, 5, 6, 7};
        array3 = shift.arrayKleft(array3, 2);
        Arrays.stream(array3).forEach(o -> {
            System.out.print(o);
            System.out.print(" ");
        });

    }
}
